import functools
from Frame import Frame
from collections import namedtuple
import time

from TemplateSolver import TemplateSolver

#Pair数据结构, 第一个参数代表边(步伐), 第二个参数代表评分
Pair = namedtuple('Pair', ['edge', 'utility'])

__MIN__ = -1000000000
__MAX__ = 1000000000
__MOVE_TIME__ = 10


class ABSolver(TemplateSolver):
    def __init__(self) -> None:
        super().__init__(self.ab_gen_next_step)

    def solve(self, frame: Frame):
        # if frame.current_board.get_box_count(2) == 25:
        #     print('+++flag+++')
        return self.ab_gen_next_step(frame)

    def ab_gen_next_step(self, frame: Frame) -> tuple:
        """使用阿尔法贝塔剪枝算法生成下一步

        Args:
            frame (Frame): 回合帧

        Returns:
            tuple: 步伐
        """
        self.nc = 0
        self.start_time = time.time()
        # if self.reference_player == -1:
        self.reference_player = frame.current_round
        self.max_level = 1
        best_step = None
        while self.max_level <= len(frame.current_board.get_available_step()):
            pair = self.dfs(frame, frame.current_round, __MIN__, __MAX__, 0)
            # 一直搜索, 直到时间结束或者到达底层
            if time.time() - self.start_time < __MOVE_TIME__:
                best_step = pair.edge
            else:
                break
            # 记录当前深度
            self.max_level += 1
            print(f"{pair.edge}")
        print(self.nc)
        return best_step

    def dfs(self, frame: Frame, current_player: int, a: int, b: int, level: int) -> Pair:
        self.nc += 1
        # 当深度小于max_level 并且没有超过时间限制时
        if level < self.max_level and (time.time() - self.start_time) < __MOVE_TIME__:
            steps = frame.current_board.get_available_step(is_shuffle=True)
            size = len(steps)

            # 当是叶子节点时, 直接返回
            if size == 0:
                return Pair(None, self.evaluate(frame, current_player))

            # 得到子节点
            neighbors: list[Pair] = []

            for i in range(size):
                # 生成子节点现场
                new_board = frame.current_board.get_new_board(
                    current_player, *steps[i])
                # new_board.check_box(current_player)
                new_round_player = current_player if new_board.get_score(
                    current_player) > frame.current_board.get_score(current_player) else frame.toggle_round(current_player)
                neighbors.append(Pair(steps[i], self.evaluate(Frame(frame.red_player, frame.blue_player, new_round_player,
                                                                    new_board.get_score(
                                                                        frame.red_player),
                                                                    new_board.get_score(
                                                                        frame.blue_player),
                                                                    new_board), new_round_player)))
            neighbors = sorted(neighbors, key=lambda x: x.utility)
            steps = []
            if self.reference_player != current_player:
                for i in range(size):
                    steps.append(neighbors[i].edge)
            else:
                for i in range(size - 1, -1, -1):
                    steps.append(neighbors[i].edge)

            # if len(steps) < 10:
            #     print(neighbors)

            if current_player == self.reference_player:
                # 当前回合是我们回合, 相当于MAX层, 我们要最大化我们的利益
                new_pair = Pair(None, __MIN__)
                for i in range(size):
                    # 遍历所有子节点
                    child_board = frame.current_board.get_new_board(
                        current_player, *steps[i])
                    pair: Pair
                    child_score = child_board.get_score(current_player)
                    current_score = frame.current_board.get_score(
                        current_player)
                    flag = False
                    if child_score == current_score:
                        pair = self.dfs(Frame(frame.red_player, frame.blue_player, frame.toggle_round(current_player),
                                              child_board.get_score(frame.red_player), child_board.get_score(
                                                  frame.blue_player),
                                              child_board), frame.toggle_round(current_player), a, b, level + 1)
                        flag = True
                    else:
                        pair = self.dfs(Frame(frame.red_player, frame.blue_player, current_player,
                                              child_board.get_score(frame.red_player), child_board.get_score(
                                                  frame.blue_player),
                                              child_board), current_player, a, b, level + 1)
                    child_utility = pair.utility
                    if new_pair.utility < child_utility:
                        new_pair = Pair(steps[i], child_utility)
                    if flag:
                        if child_utility >= b:
                            return new_pair
                    a = max(a, new_pair.utility)
                return new_pair
            else:
                # 对手回合, 相对于MIN层, 对方会最小化我们的利益
                new_pair = Pair(None, __MAX__)
                for i in range(size):
                    child_board = frame.current_board.get_new_board(
                        current_player, *steps[i])
                    pair: Pair
                    child_score = child_board.get_score(current_player)
                    current_score = frame.current_board.get_score(
                        current_player)
                    flag = False
                    if child_score == current_score:
                        pair = self.dfs(Frame(frame.red_player, frame.blue_player, frame.toggle_round(current_player),
                                              child_board.get_score(
                                                  frame.red_player),
                                              child_board.get_score(frame.blue_player), child_board),
                                        frame.toggle_round(current_player), a, b, level + 1)
                        flag = True
                    else:
                        pair = self.dfs(Frame(frame.red_player, frame.blue_player, current_player,
                                              child_board.get_score(
                                                  frame.red_player),
                                              child_board.get_score(frame.blue_player), child_board),
                                        current_player, a, b, level + 1)
                    child_utility = pair.utility
                    if new_pair.utility > child_utility:
                        new_pair = Pair(steps[i], child_utility)
                    if flag:
                        if child_utility <= a:
                            return new_pair
                    b = min(b, new_pair.utility)
                return new_pair
        else:
            return Pair(None, self.evaluate(frame, current_player))
